BZOJ2115【WC2011】Xor <线性基>

Problem

【WC2011】Xor

Description

Input

第一行包含两个整数和，表示该无向图中点的数目与边的数目。
接下来行描述条边，每行三个整数，表示与之间存在一条权值为的无向边。
图中可能有重边或自环。

Output

仅包含一个整数，表示最大的和（十进制结果），注意输出后加换行回车。

Sample Input

Sample Output

Hint

标签：线性基

Solution

线性基经典题。

对于一条非简单的路径，其异或和等于其中的简单路径异或和异或上经过的环的异或和，即选取一条简单路径和若干环，此简单路径到环的那段路径会经过两次，因而异或和消成。
因此只用选出一条从到的简单路径异或和，再异或上若干环的异或和使总和最大即可。
于是暴力找到简单路径异或和和所有环的异或和，对所有环的异或和求线性基，贪心选最大和即可。

Code

#include <bits/stdc++.h>
#define SZ 60
#define MAX_N 50000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;
lnt b[SZ+5], dis[MAX_N+5]; bool mrk[MAX_N+5];
vector <int> G[MAX_N+5]; vector <lnt> E[MAX_N+5];
void insert(lnt x) {
    for (int i = SZ; ~i; i--) if (x>>i&1) {
        if (b[i]) x ^= b[i];
        else {b[i] = x; break;}
    }
}
void DFS(int u) {
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (mrk[v = G[u][i]]) insert(dis[u]^dis[v]^E[u][i]);
        else dis[v] = dis[u]^E[u][i], mrk[v] = true, DFS(v);
}
int main() {
    read(n), read(m);
    for (int i = 0, u, v; i < m; i++) {
        lnt c;	read(u), read(v), read(c);
        G[u].push_back(v), E[u].push_back(c);
        G[v].push_back(u), E[v].push_back(c);
    }
    DFS(1);	lnt mx = dis[n];
    for (int i = SZ; ~i; i--)
        if (!(mx>>i&1)) mx ^= b[i];
    return printf("%lld\n", mx), 0;
}